DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2023.4

The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term

Authors: Erhard Aichinger and Simon Grünbacher

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract

We consider finite algebraic structures and ask whether every solution of a given system of equations satisfies some other equation. This can be formulated as checking the validity of certain first order formulae called quasi-identities. Checking the validity of quasi-identities is closely linked to solving systems of equations. For systems of equations over finite algebras with finitely many fundamental operations, a complete P/NPC dichotomy is known, while the situation appears to be more complicated for single equations. The complexity of checking the validity of a quasi-identity lies between the complexity of term equivalence (checking whether two terms induce the same function) and the complexity of solving systems of polynomial equations. We prove that for each finite algebra with a Mal'cev term and finitely many fundamental operations, checking the validity of quasi-identities is coNP-complete if the algebra is not abelian, and in P when the algebra is abelian.

Cite as

Erhard Aichinger and Simon Grünbacher. The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{aichinger_et_al:LIPIcs.STACS.2023.4,
  author =	{Aichinger, Erhard and Gr\"{u}nbacher, Simon},
  title =	{{The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.4},
  URN =		{urn:nbn:de:0030-drops-176560},
  doi =		{10.4230/LIPIcs.STACS.2023.4},
  annote =	{Keywords: quasi-identities, conditional identities, systems of equations}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2019.72

Solving Systems of Equations in Supernilpotent Algebras

Authors: Erhard Aichinger

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract

Recently, M. Kompatscher proved that for each finite supernilpotent algebra A in a congruence modular variety, there is a polynomial time algorithm to solve polynomial equations over this algebra. Let mu be the maximal arity of the fundamental operations of A, and let d := |A|^{log_2 mu + log_2 |A| + 1}. Applying a method that G. Károlyi and C. Szabó had used to solve equations over finite nilpotent rings, we show that for A, there is c in N such that a solution of every system of s equations in n variables can be found by testing at most c n^{sd} (instead of all |A|^n possible) assignments to the variables. This also yields new information on some circuit satisfiability problems.

Cite as

Erhard Aichinger. Solving Systems of Equations in Supernilpotent Algebras. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 72:1-72:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aichinger:LIPIcs.MFCS.2019.72,
  author =	{Aichinger, Erhard},
  title =	{{Solving Systems of Equations in Supernilpotent Algebras}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{72:1--72:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.72},
  URN =		{urn:nbn:de:0030-drops-110162},
  doi =		{10.4230/LIPIcs.MFCS.2019.72},
  annote =	{Keywords: Supernilpotent algebras, polynomial equations, polynomial mappings, circuit satisfiability}
}

Search Results

Documents authored by Aichinger, Erhard

The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term

Abstract

Cite as

Solving Systems of Equations in Supernilpotent Algebras

Abstract

Cite as

Thanks for your feedback!

Could not send message